1. Field of the Invention
The present invention is directed to a route search method.
2. Background of the Invention
In a route search of an electronic map, that is, in order to find a route from a departure point to a destination point (the route is, hereinafter, referred to as a specific route), Dijkstra's method has been widely used. However, according to this method, search is made in all directions from the departure point including a direction not related to the specific route, which reduces computational efficiency.
On the other hand, there are also well-known techniques for limiting a search area, or for making a directional search so that unnecessary search is omitted and almost the shortest specific route can be found for a short time. The former technique is, for example, adopted into the Japanese Patent Laid-Open Gazette No. 63-20700, while the latter, for example, into the Japanese Patent Laid-Open Gazettes Nos. 4-280287 and 2-260000.
In the route search method for limiting the search area, an area including the departure point and the destination point is set so that only the area is searched excluding an area unlikely to be included in the specific route. In the directional route search, orientation or distance to the destination point are examined whenever the route is branched at a node. Thus, the branch approaching closer to the destination point is always selected to search the specific route.
However, in the route search method for limiting the search area, the route may expand to the outside of the search area and cannot be searched. Such an example is schematically shown in FIG. 20. Though a departure point S and a destination point E are both included in a limited search area Q, a specific route R goes beyond the search area Q due to the presence of a bay therebetween. Thus, in this route search, it is necessary to set the search area large enough to include any mountains regions or bays between the departure point S and the destination point E. The search of such an area, however, increases the amount of data to be processed, and reduces computational efficiency.
In the directional route search, since the search area is not limited, geographical features between the departure point and the destination point, such as mountains regions and bays, have no influence on the search. However, in this method, the search may end as soon as the first route to the destination point is found without thoroughly reviewing other routes, or the search may take considerably a long time, not easily reaching the destination point.